package com.peng.leetcode.dynamic;

/**
 * Rob_2021_04
 * <p>
 * 213. 打家劫舍 II
 *
 * @author: lupeng6
 * @create: 2021/4/15 10:25
 */
public class Rob_2021_04 {


    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 1};
        System.out.println(new Rob_2021_04().rob(nums));
    }

    /**
     * 使用动态规划， 分别计算 0 - (size - 2)  1- (size-1)
     *
     * @author lupeng6
     * @date 2021/4/15 10:26
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robRange(0, nums.length - 2, nums), robRange(1, nums.length - 1, nums));
    }

    private int robRange(int start, int end, int[] nums) {
        int first = nums[start];
        int second = Math.max(nums[start], nums[start + 1]);

        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}
